package com.tree;

import java.util.ArrayList;

public class AVL<E extends Comparable<E>>{
    private class Node {
        private E e;
        private Node left;
        private Node right;
        private int height;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            this.height = 1;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", left=" + left +
                    ", right=" + right +
                    ", height=" + height +
                    '}';
        }
    }

    private Node root;
    private int size;

    public Integer getSize() {
        return size;
    }

    public boolean isBST(){
        ArrayList<E> arrayList = new ArrayList<>();
        midOrder(arrayList);
        for (int i = 0; i < arrayList.size()-1; i++) {
            if (arrayList.get(i).compareTo(arrayList.get(i+1))>=0)
                return false;
        }
        return true;
    }

    public void midOrder(ArrayList<E> arrayList){
        midOrder(arrayList,root);
    }

    private void midOrder(ArrayList<E> arrayList,Node root) {
        if (root == null)
            return;
        midOrder(arrayList,root.left);
        arrayList.add(root.e);
        midOrder(arrayList,root.right);
    }

    public void add(E e){
        root = add(root,e);
    }

    private Node add(Node root,E e){
        if (root == null){
            size++;
            return new Node(e);
        }

        if (e.compareTo(root.e)<0){
            root.left = add(root.left,e);
        }else if (e.compareTo(root.e)>0){
            root.right = add(root.right,e);
        }
        //计算新的高度
        root.height = 1 + Math.max(getHeight(root.left),getHeight(root.right));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(root);
        //LL
        if (balanceFactor>1&&getBalanceFactor(root.left)>0){
//            System.out.println("需要右旋来完成平衡");
            return rightRotate(root);
        }
        //RR
        if (balanceFactor<-1&&getBalanceFactor(root.right)<0){
            return leftRotate(root);
        }
        //LR
        if (balanceFactor>1&&getBalanceFactor(root.left)<0){
            //先把左子树左旋
            root.left = leftRotate(root.left);
            //在整体右旋
            return rightRotate(root);
        }
        //RL
        if (balanceFactor<-1&&getBalanceFactor(root.right)>0){
            //先把右子树右旋
            root.right = rightRotate(root.right);
            //再整体左旋
            return leftRotate(root);
        }
        return root;
    }

    /**
     * 左旋
     * @param root
     * @return
     */
    private Node leftRotate(Node root) {
        if (root == null)
            return null;
        Node r = root.right;
        Node t = root.right.left;

        root.right.left = root;
        root.right = t;

        root.height = 1 + Math.max(getHeight(root.left),getHeight(root.right));
        r.height = 1 + Math.max(getHeight(r.left),getHeight(r.right));
        return r;
    }

    /**
     * 右旋
     * @param root
     * @return
     */
    private Node rightRotate(Node root) {
        if (root == null)
            return null;
        Node l = root.left;
        Node t = root.left.right;

        root.left.right = root;
        root.left = t;

        root.height = 1 + Math.max(getHeight(root.left),getHeight(root.right));
        l.height = 1 + Math.max(getHeight(l.left),getHeight(l.right));
        return l;
    }

    public boolean isBalance(){
        return isBalance(root);
    }

    private boolean isBalance(Node root){
        if (root == null)
            return true;
        //获取平衡因子
        int bf = getBalanceFactor(root);
        //判断是否平衡
        if (Math.abs(bf)>1){
            return false;
        }else
//            {
//            if (isBalance(root.left))
//                return isBalance(root.right);
//            else
//                return false;
//        }
        //递归左子树和右子树
        return isBalance(root.left)&&isBalance(root.right);
    }

    /**
     * 获取平衡因子，左树高度减去右树高度（可正可负）
     * @param root
     * @return
     */
    private int getBalanceFactor(Node root) {
        if (root == null)
            return 0;
        else
            return getHeight(root.left)-getHeight(root.right);
    }

    private int getHeight(Node root){
        if (root == null)
            return 0;
        return root.height;

    }
    public Node deleteNode(E e){
        return deleteNode(root,e);
    }
    private Node deleteNode(Node root,E e){
        if (root == null)
            return null;
        Node returnNode = null;
        if (e.compareTo(root.e)<0){
            root.left = deleteNode(root.left,e);
        }else if(e.compareTo(root.e)>0){
            root.right = deleteNode(root.right,e);
        }else {
            if (root.left == null){
                returnNode = root.right;
            }
            if (root.right == null){
                returnNode = root.left;
            }
            if (root.left != null&&root.right != null){
                Node node = rightMin(root.right);
                root.e = node.e;
                root.right = deleteNode(root.right,e);
                returnNode = root;
            }
        }
        //LL
        int balanceFactor = getBalanceFactor(returnNode);
        if (balanceFactor>1&&getBalanceFactor(returnNode.left)>=0){
            returnNode = rightRotate(returnNode);
        }
        //RR
        if (balanceFactor<-1&&getBalanceFactor(returnNode.right)>=0){
            returnNode = leftRotate(returnNode);
        }
        //LR
        if (balanceFactor>1&&getBalanceFactor(returnNode.left)<0){
            returnNode.right = leftRotate(returnNode.right);
            returnNode = rightRotate(returnNode);
        }
        //RL
        if (balanceFactor<-1&&getBalanceFactor(returnNode.left)>=0){
            returnNode.left = rightRotate(returnNode.left);
            returnNode = leftRotate(returnNode);
        }
        return returnNode;

    }

    private Node rightMin(Node right) {
        if (right == null||right.left == null)
            return right;
        return rightMin(right.left);
    }




}
